// https://leetcode.cn/problems/climbing-stairs/
#include <iostream>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
		// 动态规划
		if(n <= 2){
			return n;
		}
		int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
		for(int i = 3; i <= n; i++){
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[n];
    }
	
	// 递归方法会导致内存溢出
	int back(int n){
		if(n <= 2){
			return n;
		}
		return back(n-1) + back(n-2);
	}
};

int main(){
	Solution so;
	int a = so.climbStairs(45);
	cout << a << endl;
	return 0;
}